Lịch sử tiến hóa và các mối quan hệ giữa các họ trong bộ vẫn còn là điều bí ẩn cho tới tận gần đây. Nhiều họ được gộp nhóm cùng nhau trên cơ sở các nét tương đồng hình thái mà hiện nay người ta tin rằng chỉ là kết quả của tiến hóa hội tụ chứ không phải là do có quan hệ di truyền gần gũi. Ví dụ, các loài chim "hồng tước" ở Bắc bán cầu, ở Australia và ở New Zealand trông rất tương tự và chúng có cung cách sinh sống cũng tương tự, nhưng thuộc về ba nhánh xa nhau trong cây phát sinh loài của bộ Sẻ; chúng không có quan hệ họ hàng gần như vẫn tưởng mà chỉ cùng nằm trong bộ Sẻ mà thôi.

Cần phải có thêm nhiều nghiên cứu, nhưng những tiến bộ trong sinh học phân tử và các dữ liệu cổ địa sinh học ngày càng hoàn thiện dần dần sẽ cho thấy hình ảnh rõ ràng hơn về nguồn gốc và tiến hóa của các loài chim dạng sẻ. Hiện nay, người ta cho rằng những loài chim dạng sẻ đầu tiên đã tiến hóa tại Gondwana vào thời gian trong kỷ Paleogen, có thể là khoảng Hậu Paleocen cỡ 60–55 Ma. Sự chia tách ban đầu là giữa Tyranni, các dạng chim biết hót, Eurylaimides và "hồng tước" New Zealand, có thể đã phân ra trong khoảng thời gian ngắn (nhiều nhất là vài triệu năm). Bộ Sẻ dường như cũng đã tiến hóa ra ngoài để thành các nhánh có quan hệ tương đối gần ("cận chim sẻ") như các nhánh chứa Piciformes (các dạng gõ kiến), Coraciiformes (các dạng sả) và Cuculiformes (các dạng cu cu).[1]

Muộn hơn một chút, sự phân tỏa lớn các dạng diễn ra tại khu vực ngày nay là Australia-New Guinea: Passeri hay chim biết hót. Nhánh chính của Passeri, tiểu bộ "Passerida", đã nổi lên hoặc như là nhóm chị-em với dòng dõi cơ sở và nhóm dạng quạ (tiểu bộ "Corvida"), hoặc có thể nhiều hơn là một phân nhóm của nó, mở rộng sâu vào đại lục Á-Âu và châu Phi, tại đó lại tiếp tục có sự phân tỏa lớn sinh ra các dòng dõi mới. Điều này cuối cùng dẫn tới 3 dòng dõi chính trong bộ Sẻ bao gồm khoảng 4.000 loài, cùng với nhánh Corvida và hàng loạt các nhánh nhỏ khác tạo thành sự đa dạng của chim biết hót ngày nay. Cũng diễn ra sự phối trộn địa sinh học trên phạm vi rộng, với các dạng phía bắc quay về phía nam còn các dạng phía nam thì di chuyển lên phía bắc v.v.

Mẫu hóa thạch

Các dạng sẻ sớm nhất
Nghiên cứu về xương các loài chim đậu, đặc biệt là các xương chi, chỉ mang tính chất chẩn đoán.[2] Tuy nhiên, các mẫu hóa thạch sớm là ít do các dạng chim dạng sẻ đầu tiên dường như là ở phía nhỏ của khoảng kích cỡ ngày nay và các xương mỏng mảnh của chúng không được bảo quản tốt. Các mẫu vật của Viện bảo tàng Queensland số F20688 (carpometacarpus) và F24685 (xương đầu gối) từ Murgon, Queensland là các mảnh xương hóa thạch rất dễ dàng nhận ra là có dạng sẻ; chúng đại diện cho hai loài với kích thước chiều dài tổng thể khoảng 10 tới 20 cm và chứng minh rằng vào khoảng 55 Ma, gần với Tiền Eocen, các dạng chim đậu nguyên thủy đã có sự khác biệt có thể nhận ra.[3] Một nhóm tương tự, Zygodactylidae (đặt tên theo khả năng tiếp cận bằng ngón (zygodactyly) để đậu) đã phát sinh độc lập có thể cùng khoảng thời gian này – và có thể từ các tổ tiên có quan hệ gần – tại các vùng đất tiếp giáp với Bắc Đại Tây Dương, khi đó chỉ có bề rộng cỡ 2/3 bề rộng ngày nay.

Cho đến khi có phát hiện ra các hóa thạch ở Australia, người ta tin rằng Palaeospiza bella từ tầng hóa thạch Florissant Priabona (Hậu Eocen, khoảng 35 Ma) là chim dạng sẻ cổ nhất đã biết. Tuy nhiên, hiện nay người ta coi nó thuộc về nhóm cận chim sẻ không có dạng sẻ.

Từ thành hệ Bathans tại sông Manuherikia ở Otago, New Zealand, MNZ S42815 (ngoại biên xương cổ chân phải của loài chim có kích thước cỡ chim tui (Prosthemadera novaeseelandiae)) và một vài xương của ít nhất là một loài chim kích thước cỡ chim yên ngựa (Philesturnus carunculatus) đã được mô tả gần đây. Chúng có niên đại từ khoảng Tiền tới Trung Miocen (tầng Awamoan tới tầng Lillburnian, khoảng 19-16 Ma).[4]

Kiến thức hiện nay về các mối liên-quan hệ của các nhóm chim dạng sẻ còn sinh tồn cho thấy tổ tiên chung gần nhất của mọi chim dạng sẻ còn sinh tồn là một loài chim rừng nhỏ, có lẽ với đuôi ngắn và mập[5] và màu nâu xám tổng thể, nhưng có thể với dị hình lưỡng tính rõ ràng. Đặc điểm sau dường như đã bị mất và tái tiến hóa nhiều lần chỉ riêng ở quá trình tiến hóa của chim biết hót, được phán đoán từ phân bố của đặc điểm này trong các dòng dõi còn sinh tồn: chẳng hạn tổ tiên chung của Passerida gần như chắc chắn là không có dị hình lưỡng tính rõ ràng khi xem xét tới việc đặc điểm này là rất hiếm trong số các dòng dõi cơ sở của nó, nhưng rất phổ biến trong nhánh Passerida trẻ hơn, nhóm Passeroidea; ngược lại trong số các dòng dõi cơ sở nhất của Passeri thì có một lượng đáng kể các dòng dõi có dị hình mạnh, chẳng hạn họ Menuridae rất cổ cũng như nhiều nhóm trong Meliphagoidea và Corvoidea. Dị hình lưỡng tính cũng không là hiếm ở Acanthisittidae và rõ nét ở một số chim gần biết hót như Pipridae và Cotingidae.

Các dạng sẻ sớm ở châu Âu
Tại châu Âu, các loài chim đậu là không quá hiếm trong các mẫu hóa thạch từ thế Oligocen trở đi, nhưng phần lớn là quá rời rạc để có thể xác định vị trí dứt khoát hơn:

• Wieslochia (Tiền Oligocen ở Frauenweiler, Đức)
• Passeriformes chi mơ hồ loài không rõ ràng (gen. et sp. indet.) (Tiền Oligocen ở Luberon, Pháp) – gần biết hót hay cơ sở[6]
• Passeriformes chi mơ hồ loài không rõ ràng (Hậu Oligocen ở Pháp) – một vài đơn vị phân loại cận biết hót và biết hót[7]
• Passeriformes chi mơ hồ loài không rõ ràng (Trung Miocen ở Pháp và Đức) – cơ sở?[8]
• Passeriformes chi mơ hồ loài không rõ ràng (Sajóvölgyi Trung Miocen ở Mátraszõlõs, Hungary) – ít nhất 2 đơn vị phân loại, có thể là 3; ít nhất một trong đó là chim biết hót[9]

Wieslochia có thể không là thành viên của bất kỳ phân bộ còn sinh tồn nào. Điều đó nghĩa là không chỉ có nhóm Passeri là đã mở rộng ra ngoài khu vực phát sinh của nó và được chứng minh bằng hóa thạch của chim mỏ rộng không xác định (họ Eurylaimidae) từ Tiền Miocen (khoảng 20 Ma) ở Wintershof, Đức và của chim cận biết hót danh pháp không xác định Hậu Oligocen tại Pháp như liệt kê trên đây. Thậm chí các dạng chim dạng sẻ rất cơ sở có thể cũng là phổ biến tại châu Âu cho tới Trung Miocen, vào khoảng 12 Ma.[10] Các siêu họ còn sinh tồn của nhóm Passeri cũng đã rất khác biệt vào thời gian đó và được biết kể từ khoảng 12–13 Ma khi các chi hiện đại đã có mặt trong nhóm Corvoidea và chim biết hót cơ sở. Sự đa dạng hiện nay của các chi Passerida được biết đến chủ yếu từ Hậu Miocen trở đi và trong thế Pliocen (khoảng 10–2 Ma). Các khu hệ hóa thạch thế Pleistocen và đầu thế Holocen (<1,8 Ma) chứa hóa thạch của nhiều loài hiện còn sinh tồn, và nhiều khu chỉ chứa hóa thạch của các loài còn sinh tồn hoặc loài thời gian và các phân loài cổ của chúng.

Hóa thạch châu Mỹ
Tại châu Mỹ, các mẫu hóa thạch là hiếm hơn trước thế Pleistocen, từ đó một vài họ chim cận biết hót hiện vẫn còn tồn tại đã được chứng minh. Bên cạnh mẫu vật không thể xác định MACN-SC-1411 (Pinturas, Tiền/Trung Miocen ở tỉnh Santa Cruz, Argentina),[11] thì dòng dõi đã tuyệt chủng của các dạng chim đậu đã được mô tả từ thời gian Hậu Miocen ở California, Hoa Kỳ: Palaeoscinidae với một chi Paleoscinis. "Palaeostruthus" eurius (Pliocen ở Florida) có lẽ thuộc về họ còn sinh tồn, có thể nhất là Passeroidea.